#include <bits/stdc++.h>
using namespace std;

/*
3487. 删除后的最大子数组元素和
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 。

你可以从数组 nums 中删除任意数量的元素，但不能将其变为 空 数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组：

子数组中的所有元素 互不相同 。
最大化 子数组的元素和。
返回子数组的 最大元素和 。

子数组 是数组的一个连续、非空 的元素序列。
 

示例 1：

输入：nums = [1,2,3,4,5]

输出：15

解释：

不删除任何元素，选中整个数组得到最大元素和。

示例 2：

输入：nums = [1,1,0,1,1]

输出：1

解释：

删除元素 nums[0] == 1、nums[1] == 1、nums[2] == 0 和 nums[3] == 1 。选中整个数组 [1] 得到最大元素和。

示例 3：

输入：nums = [1,2,-1,-2,1,0,-1]

输出：3

解释：

删除元素 nums[2] == -1 和 nums[3] == -2 ，从 [1, 2, 1, 0, -1] 中选中子数组 [2, 1] 以获得最大元素和。

 

提示：

1 <= nums.length <= 100
-100 <= nums[i] <= 100
*/

// 法一
class Solution {
public:
    int maxSum(vector<int>& nums) {
        // set 可以直接去重
        unordered_set<int> uniqueNum;
        int max_sum = 0;
        // 当前最大负数 也就是防止未找到 初始化最小整数
        int maxNeg = INT_MIN;

        for (int n : nums) {
            // 负数 就更新
            if (n < 0) maxNeg = max(maxNeg, n);
            // 非负数 不在集合中  那么累加进去
            else if (uniqueNum.insert(n).second)    max_sum += n;
        }

        // 集合是空的 那么就是全是空的 直接返回
        if (uniqueNum.empty())  return maxNeg;
        else    return max_sum;
    }
};

// 法二
class Solution {
public:
    int maxSum(vector<int>& nums) {
        // 创建一个无序集合st，用于存储已经出现过的正整数，以实现去重
        unordered_set<int> st;
        // res用于存储去重后的正整数的总和，初始化为0
        int res = 0;
        // ma用于存储向量nums中的最大负数，初始化为一个较小的值 -1005
        int ma = -1005;
        // 遍历向量nums中的每一个元素ele
        for (int& ele : nums) {
            // 更新ma为当前ma和ele中的较大值，这样ma始终保持为遍历过的元素中的最大负数
            ma = max(ma, ele);
            // 如果ele是正数且在集合st中不存在
            if (ele > 0 &&!st.count(ele)) {
                // 将ele插入到集合st中
                st.insert(ele);
                // 将ele累加到res中
                res += ele;
            }
        }
        // 如果最大负数ma小于0，说明向量nums中所有元素都是负数，返回ma
        // 否则，返回去重后的正整数的总和res
        return ma < 0? ma : res;
    }
};